package 二叉树的下一结点;
//题目描述
//给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
// 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
public class Solution
{
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        //三种情况，1.有右子树，则下一结点是右子树的最左子节点
        //2.无右子树，则是父节点
        //3.无右子树，且是其父节点的右子节点，则向上找，直到找到一个节点，他是他的父节点的左子节点，那么下一个节点就是这个父节点
        //其中，2,3，可以在代码中写在一起

        //判断输入
        if (pNode==null)
            return null;
        TreeLinkNode pnext=null;
        if (pNode.right!=null)
        {
            TreeLinkNode pright=pNode.right;
            while (pright.left!=null)
            {
                pright=pright.left;
            }
            pnext=pright;
        }
        else if (pNode.next!=null)
        {
            TreeLinkNode pCurrent=pNode;
            TreeLinkNode pParent=pNode.next;
            while (pParent!=null&&pCurrent==pParent.right)
            {
                pCurrent=pParent;
                pParent=pParent.next;
            }
            pnext=pCurrent;
        }
        return pnext;
    }
}
